#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    unordered_map<int, string> map;

    public:
    //out of time
    string ans1(string s){
        int len = s.size();
        int index = 0;
        if(len == 1){
            return s;
        }
        
        for(int i = 0; i != len-1; i++){
            string temp = "";
            temp = temp + s[i];
            for(int j = i+1; j != len; j++){
                temp = temp + s[j];
                if(s[i] == s[j]){
                    string re = temp;
                    reverse(re.begin(), re.end());
                    if(temp == re && (int)temp.size() > index){
                        index = max((int)temp.size(), index);
                        map[index] = temp;
                    }
                }
            }
            if(index == 0){
                temp.pop_back();
                string re = temp;
                reverse(re.begin(), re.end());
                if(temp == re){
                    index = max((int)temp.size(), index);
                    map[index] = temp;
                }
            }
        }

        return map[index];
    }

    string ans2(string s){
        int len = s.size();
        if(len == 1){
            return s;
        }

        vector<vector<bool>> dp(len, vector<bool>(len));
        for(int i = 0; i != len; i++){
            dp[i][i] = true;
        }
        
        int maxLen = 1;
        int begin = 0;
        for(int L = 2; L != len+1; L++){
            for(int i = 0; i != len; i++){
                int j = L + i - 1;
                if(j >= len){
                    break;
                }

                if(s[i] != s[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substr(begin, maxLen);
    }
};

void test1(){
    Solution s;
    string str = "babad";

    // string ret = s.ans1(str);
    string ret = s.ans2(str);
    cout << ret << endl;
}

void test2(){
    Solution s;
    string str = "cbbd";

    // string ret = s.ans1(str);
    string ret = s.ans2(str);
    cout << ret << endl;
}

void test3(){
    Solution s;
    string str = "lphntrsqudccteewsdmpjmgmfnxegawjclzobpnxdrvxeygafiwyqsvsecictqkmiqvrdjajfngvlhdezdpqpzjjzbhoyggrbkuzeocrpzqishvfairdvvabopyubfisxbrgnlughbrzunitwowvnsqhdtnkotitgxwzjhbgltksorygpdberdgzgvogrvwluhixfbrfhliedjylxuspjpitwlhdkneonreqrueqphirmgxtqumllqropaefddplspkrtkbmuvwkyryworojlvwzdlacuoqzokrmcgmwkopsbqjjkaoqjqbrderwzmhbhfgwvrjakyfeqcbtvlcgbsxkngymxyievihiskdmmppmmdksihiveiyxmygnkxsbgclvtbcqefykajrvwgfhbhmzwredrbqjqoakjjqbspokwmgcmrkozqoucaldzwvljorowyrykwvumbktrkpslpddfeaporqllmuqtxgmrihpqeurqernoenkdhlwtipjpsuxlyjdeilhfrbfxihulwvrgovgzgdrebdpgyrosktlgbhjzwxgtitokntdhqsnvwowtinuzrbhgulngrbxsifbuypobavvdriafvhsiqzprcoezukbrggyohbzjjzpqpdzedhlvgnfjajdrvqimkqtcicesvsqywifagyexvrdxnpbozlcjwagexnfmgmjpmdsweetccduqsrtnhpl";

    // string ret = s.ans1(str);
    string ret = s.ans2(str);
    cout << ret << endl;
}

void test4(){
    Solution s;
    string str = "ccc";

    // string ret = s.ans1(str);
    string ret = s.ans2(str);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();
    test4();

    return 0;
}